public class test3_Optimized {public static void main(String[] args) {
    int maxNum = 20000;
    boolean[] isPrimeArr = new boolean[maxNum + 1];
    // 初始化：默认所有数为素数
    for (int i = 0; i <= maxNum; i++) {
        isPrimeArr[i] = true;
    }
    // 标记0和1为非素数
    isPrimeArr[0] = isPrimeArr[1] = false;

    // 埃氏筛核心：标记非素数
    for (int i = 2; i <= Math.sqrt(maxNum); i++) {
        if (isPrimeArr[i]) { // 若i是素数，标记其倍数为非素数
            for (int j = i * i; j <= maxNum; j += i) { // 从i²开始标记，减少重复操作
                isPrimeArr[j] = false;
            }
        }
    }

    // 输出素数（每行5个）
    int primeCount = 0;
    System.out.println("1~20000内的素数（埃氏筛优化版，每行5个）：");
    for (int i = 2; i <= maxNum; i++) {
        if (isPrimeArr[i]) {
            System.out.print(i + "\t");
            primeCount++;
            if (primeCount % 5 == 0) {
                System.out.println();
            }
        }
    }
    System.out.println("\n1~20000内共有 " + primeCount + " 个素数");
}
}
